﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
// 原题连接：https://leetcode.cn/problems/maximum-length-of-repeated-subarray/
/*
题目描述：
给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。



示例 1：
输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3,2,1] 。

示例 2：
输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
输出：5
 

提示：
1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 100
*/


// 开始解题：
// 方法1——暴力法
int findLength(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int i = 0;
    int j = 0;
    int max_len = 0;
    int n = 0;
    for (i = 0; i < nums1Size; i++) {
        for (j = 0; j < nums2Size; j++) {
            n = 0;
            while ((i + n < nums1Size) && (j + n < nums2Size)) {
                if (nums1[i + n] == nums2[j + n]) {
                    n++;
                }
                else {
                    break;
                }
            }
            if (n > max_len) {
                max_len = n;
            }
        }
    }
    return max_len;
}
// 时间复杂度：O(n^3)，n为两个数组的平均长度。
// 空间复杂度：O(1)，我们只需要用到常数级的额外空间。